{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Happy Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isHappy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #快乐数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个算法来判断一个数 <code>n</code> 是不是快乐数。</p>\n",
    "\n",
    "<p><strong>「快乐数」</strong>&nbsp;定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。</li>\n",
    "\t<li>然后重复这个过程直到这个数变为 1，也可能是 <strong>无限循环</strong> 但始终变不到 1。</li>\n",
    "\t<li>如果这个过程 <strong>结果为</strong>&nbsp;1，那么这个数就是快乐数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果 <code>n</code> 是 <em>快乐数</em> 就返回 <code>true</code> ；不是，则返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 19\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：\n",
    "</strong>1<sup>2</sup> + 9<sup>2</sup> = 82\n",
    "8<sup>2</sup> + 2<sup>2</sup> = 68\n",
    "6<sup>2</sup> + 8<sup>2</sup> = 100\n",
    "1<sup>2</sup> + 0<sup>2</sup> + 0<sup>2</sup> = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [happy-number](https://leetcode.cn/problems/happy-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [happy-number](https://leetcode.cn/problems/happy-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['19', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def iteration(n):\n",
    "            ans = 0\n",
    "            for i in str(n):\n",
    "                ans+= int(i)**2\n",
    "            return ans\n",
    "        seen = set()\n",
    "        while(1):\n",
    "            if n==1:\n",
    "                return True\n",
    "            if n in seen:\n",
    "                return False\n",
    "            seen.add(n)\n",
    "            n = iteration(n)\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dict={1:1, 7:1, 10:1, 13:1, 19:1, 23:1, 28:1, 31:1, 32:1, 44:1, 49:1, 68:1, 70:1, 79:1, 82:1, 86:1, 91:1, 94:1, 97:1, 100:1}\n",
    "        while n>100:\n",
    "            s=str(n)\n",
    "            n=0\n",
    "            for i in s:\n",
    "                n+=int(i)**2\n",
    "        return n in dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        cur,hashmap=n,{}\n",
    "        \n",
    "        while cur not in hashmap:\n",
    "            if cur==1:\n",
    "                return True\n",
    "        \n",
    "            hashmap[cur]=1\n",
    "            \n",
    "            temp=cur\n",
    "            cur=0\n",
    "            while temp:\n",
    "                cur+=(temp%10)**2\n",
    "                temp=int(temp/10)\n",
    "            \n",
    "            \n",
    "        return False\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        store = set()\n",
    "        \n",
    "        def sub(n):\n",
    "            nlst = []\n",
    "            while n:\n",
    "                mod = n%10\n",
    "                n = n//10\n",
    "                nlst.append(mod)\n",
    "            result = sum([m**2 for m in nlst])\n",
    "            if result == 1:\n",
    "                return True\n",
    "            else:\n",
    "                if result in store:\n",
    "                    return False\n",
    "                else:\n",
    "                    store.add(result)\n",
    "                    return sub(result)\n",
    "        return sub(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        \n",
    "        while n != 1 and (n not in res):\n",
    "            res.append(n)\n",
    "            n = self.calculate(n)\n",
    "            \n",
    "        if n == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def calculate(self, n):\n",
    "        res = 0\n",
    "        for i in list(str(n)):\n",
    "            res += int(i) ** 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "\n",
    "        while True:\n",
    "\n",
    "  \n",
    "            n = sum(int(i)**2 for i in str(n))\n",
    "\n",
    "            if n == 1:\n",
    "                return True\n",
    "            elif n == 4 :\n",
    "                return False\n",
    "     \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "\n",
    "        while True:\n",
    "            s = 0\n",
    "            while  (n>0):\n",
    "                num = n % 10\n",
    "                s += num**2\n",
    "                n = n//10\n",
    "            n = s\n",
    "            if s == 1:\n",
    "                return True\n",
    "            elif s == 4 :\n",
    "                return False\n",
    "     \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        result=[]\n",
    "        target=True\n",
    "        while target:\n",
    "            print(n)\n",
    "            if n in result:\n",
    "                target=False\n",
    "            else:\n",
    "                result.append(n)\n",
    "            n=self._isHappy(n)\n",
    "            if n==1:\n",
    "                break\n",
    "        return target\n",
    "        \n",
    "    def _isHappy(self,n):\n",
    "        tmp=0\n",
    "        while n:\n",
    "            tmp+=pow(n%10,2)\n",
    "            n=n//10\n",
    "        return tmp\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        def happySum(n):\n",
    "            sum = 0\n",
    "            while n:\n",
    "                sum += int(n%10)**2\n",
    "                n = int(n/10)\n",
    "            return sum\n",
    "        self.s = {}\n",
    "        while n != 1:\n",
    "            print(n)\n",
    "            n = happySum(n)\n",
    "            if n in self.s:\n",
    "                break\n",
    "            else:\n",
    "                self.s[n] = True\n",
    "\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.temp = []\n",
    "    def isHappy(self, n: 'int') -> 'bool':\n",
    "        print(n)\n",
    "        _next_num = sum([int(i) ** 2 for i in str(n)])\n",
    "        if _next_num == 1:\n",
    "            return True\n",
    "        if _next_num in self.temp:\n",
    "            return False\n",
    "        self.temp.append(_next_num)\n",
    "        return self.isHappy(_next_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        unhappy=[4,16,37,58,89,145,42,20]\n",
    "        \n",
    "        #此函数求一个数各个位上的数，返回一个列表\n",
    "        def to_digit(num):\n",
    "            digits=[]\n",
    "            while num>=1:\n",
    "                num,rem=divmod(num,10)\n",
    "                digits.append(rem)\n",
    "            return digits\n",
    "        \n",
    "        #此函数求列表各元素的平方和，返回一个数\n",
    "        def quadratic_sum(li):\n",
    "            sum_=0\n",
    "            for i in li:\n",
    "                sum_+=i**2\n",
    "            return sum_\n",
    "        \n",
    "        res=quadratic_sum(to_digit(n))\n",
    "        while res!=1:\n",
    "            if res in unhappy:return False\n",
    "            res=quadratic_sum(to_digit(res)) \n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.base = {4, 16, 37, 58, 89, 145, 42, 20}\n",
    "        sums = sum(map(lambda x:x**2, map(int, str(n))))\n",
    "        if sums in self.base:\n",
    "            return False\n",
    "        if sums != 1:\n",
    "            return self.isHappy(sums)\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        i=n\n",
    "        while True:\n",
    "            lst=[int(f) for f in str(i)]\n",
    "            i=sum([k**2 for k in lst])\n",
    "            if i==4:\n",
    "                return False\n",
    "            if i==1:\n",
    "                return True\n",
    "      \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        self.base = {4:0, 16:0, 37:0, 58:0, 89:0, 145:0, 42:0, 20:0}\n",
    "        sums = sum(map(lambda x:x**2, map(int, str(n))))\n",
    "        if sums in self.base:\n",
    "            return False\n",
    "        if sums == 1:\n",
    "            return True\n",
    "        return self.isHappy(sums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        while n!=1:\n",
    "            nList = [int(i)**2 for i in str(n)]\n",
    "            n = sum(nList)\n",
    "            count += 1\n",
    "            if count > 9:\n",
    "                return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def trans_num(l):\n",
    "            return sum([int(i)**2 for i in str(l)])\n",
    "        show_num = set()\n",
    "        while n != 1:\n",
    "            n = trans_num(n)\n",
    "            if n not in show_num:\n",
    "                show_num.add(n)\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        hash_dict = {}\n",
    "        while 1:\n",
    "            sums = sum(map(lambda x:x**2, map(int, str(n))))\n",
    "            if sums==1:\n",
    "                return True\n",
    "            if sums in hash_dict:\n",
    "                return False\n",
    "            else:\n",
    "                hash_dict[sums]=0\n",
    "            n = sums\n",
    "            if sums==1:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        from functools import reduce\n",
    "        history = set()\n",
    "        i = n\n",
    "        while i not in history:\n",
    "            history.add(i)\n",
    "            #print(history)\n",
    "            i = reduce(lambda x,y:int(x)+int(y)*int(y), str(i), 0)\n",
    "            if 1 in history:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        while n != 4 and n != 1:\n",
    "            n = sum(int(i) ** 2 for i in str(n))\n",
    "        if n == 4:\n",
    "            return False\n",
    "        elif n == 1:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        string = str(n)\n",
    "        ans = 0\n",
    "        while n != 0:\n",
    "            for i in string:\n",
    "                ans += (int(i))**2\n",
    "            if ans == 1:\n",
    "                return True\n",
    "                break\n",
    "            if ans == 4:\n",
    "                return False\n",
    "                break\n",
    "            string = str(ans)\n",
    "            ans = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        log = set()\n",
    "\n",
    "        while n not in log:\n",
    "            log.add(n)\n",
    "            n = str(n)\n",
    "            n = sum([int(i)**2 for i in n])\n",
    "            if n == 1:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        \n",
    "        count = 0\n",
    "        while True:\n",
    "            \n",
    "            res = 0\n",
    "            s = str(n)\n",
    "            lens = len(s)\n",
    "            for i in range(lens):\n",
    "                res += int(s[i])**2\n",
    "            if res == 1:\n",
    "                return True\n",
    "            n = res\n",
    "            \n",
    "            count += 1\n",
    "            if count >10:\n",
    "                return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "就像跑步一样，快乐数跑的是100m冲刺，非快乐数则是在1个400米的环形跑道里无休止的跑下去。\n",
    "快慢指针就像是专业运动员和业务运动员，在100m的跑道上，两个都会跑到1. 而在环形跑道上，两个指针虽然见面了，但是估计慢指针才跑完一圈，快指针已经跑完两圈了\n",
    "\"\"\"\n",
    "#########111  set集合 待优化\n",
    "# class Solution:\n",
    "#     def isHappy(self, n: int) -> bool:\n",
    "#       visited = set()\n",
    "#       while n:\n",
    "#         if n in visited and n != 1:\n",
    "#           return False\n",
    "#         elif n in visited and n == 1:\n",
    "#           return True\n",
    "#         visited.add(n)\n",
    "#         n = sum(int(i)**2 for i in str(n))\n",
    "#########111  set集合 优化\n",
    "# class Solution: \n",
    "#     def isHappy(self, n: int) -> bool:\n",
    "#       visited = {1}\n",
    "#       while n not in visited:\n",
    "#         visited.add(n)\n",
    "#         n = sum(int(i)**2 for i in str(n))\n",
    "#       return n == 1\n",
    "######2222 数学法 + 尾递归\n",
    "\"\"\"\n",
    "不是快乐数的数称为不快乐数(unhappy number)，所有不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中\n",
    "已知规律： [1 ~ 4] 中只有 1 是快乐数，[5 ~ ∞] 的数字要么回归到 1 要么回归到 4 或 3\n",
    "因此仅需在 n > 4 时调用递归\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "      return self.isHappy(sum(int(i) ** 2 for i in str(n))) if n > 4 else n == 1\n",
    "############快慢指针\n",
    "\"\"\"\n",
    "使用“快慢指针”思想找出循环：“快指针”每次走两步，“慢指针”每次走一步，当二者相等时，即为一个循环周期。此时，判断是不是因为1引起的循环，是的话就是快乐数，否则不是快乐数。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "      slow = n\n",
    "      fast = sum(int(i) ** 2 for i in str(n))\n",
    "      fast = sum(int(i) ** 2 for i in str(fast))\n",
    "      while slow != fast:\n",
    "        slow = sum(int(i) ** 2 for i in str(slow))\n",
    "        fast = sum(int(i) ** 2 for i in str(fast))\n",
    "        fast = sum(int(i) ** 2 for i in str(fast))\n",
    "      return slow == 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        sumList = []\n",
    "        str_N = str(n)\n",
    "        sum_N = 0\n",
    "        while 1:\n",
    "            for i in str_N:\n",
    "                sum_N += int(i)**2\n",
    "            \n",
    "            if sum_N == 1:\n",
    "                return True\n",
    "            elif sum_N in sumList:\n",
    "                return False\n",
    "            sumList.append(sum_N)\n",
    "            str_N = str(sum_N)\n",
    "            sum_N = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        c={1}\n",
    "        while n not in c:\n",
    "            c.add(n)\n",
    "            j=0\n",
    "            for i in str(n):\n",
    "                j+=int(i)**2\n",
    "            n=j\n",
    "        if n==1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        seen = {1}\n",
    "        while n not in seen:\n",
    "            seen.add(n)\n",
    "            n = sum(int(i)**2 for i in str(n))\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        seen = {1}\n",
    "        while n not in seen:\n",
    "            seen.add(n)\n",
    "            n = sum(int(i)**2 for i in str(n))\n",
    "        return n == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "\n",
    "        def get_next(n):\n",
    "            total_sum = 0\n",
    "            while n > 0:\n",
    "                digit = n % 10\n",
    "                n //= 10\n",
    "                total_sum += digit ** 2\n",
    "            return total_sum\n",
    "\n",
    "        seen = set()\n",
    "        while n != 1 and n not in seen:\n",
    "            seen.add(n)\n",
    "            n = get_next(n)\n",
    "            print(n)\n",
    "\n",
    "        return n == 1\n",
    "    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        result = 0\n",
    "        a = []\n",
    "        while(n != 1):\n",
    "            while(n>0):\n",
    "                result += (n%10) * (n%10)\n",
    "                n = n//10\n",
    "            n  = result\n",
    "            if(len(a) == 0):\n",
    "                a.append(n)\n",
    "            else:\n",
    "                for i in range(len(a)):\n",
    "                    if(a[i] == n):\n",
    "                        return False\n",
    "                    else:\n",
    "                        a.append(n)\n",
    "            result = 0\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    num = 0 \n",
    "\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        self.num += 1\n",
    "        str_n = str(n)\n",
    "        num = int()\n",
    "        for i in range(len(str_n)):\n",
    "            num += int(str_n[i]) ** 2\n",
    "        res = self.isHappy(num) if self.num < 995 else False\n",
    "        return True if num == 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        def calculate_happy(num):\n",
    "            sum_ = 0\n",
    "            \n",
    "            # 从个位开始依次取，平方求和\n",
    "            while num:\n",
    "                sum_ += (num % 10) ** 2\n",
    "                num = num // 10\n",
    "            return sum_\n",
    "\n",
    "        # 记录中间结果\n",
    "        record = set()\n",
    "        while True:\n",
    "            n = calculate_happy(n)\n",
    "            if n == 1:\n",
    "                print(record)\n",
    "                return True\n",
    "            \n",
    "            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数\n",
    "            if n in record:\n",
    "                return False\n",
    "            else:\n",
    "                record.add(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        res = set()\n",
    "        # res.add(n)\n",
    "        \n",
    "        while(n != 1 and  n not in res):\n",
    "            sum = 0\n",
    "            res.add(n)\n",
    "            while(n):\n",
    "                sum += (n % 10) ** 2\n",
    "                n //= 10\n",
    "            n = sum\n",
    "            \n",
    "\n",
    "        if n == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n):\n",
    "        n = str(n)\n",
    "        o =0\n",
    "        while int(n)%1 ==0:\n",
    "            o+=1\n",
    "            if o >=10:\n",
    "                return False\n",
    "            zan = 0\n",
    "            for b in n:\n",
    "                zan += int(b)**2\n",
    "            n = str(zan)\n",
    "            if n == '1':\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        ans = {}\n",
    "        while n!=1:\n",
    "            a = self.calculate(n)\n",
    "            if a in ans:\n",
    "                return False\n",
    "            else:\n",
    "                ans[a]=1\n",
    "                n=a\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def calculate(self,n):\n",
    "        ans = 0\n",
    "        while n!=0:\n",
    "            ans += (n%10)**2\n",
    "            n //= 10\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        p,q = n,n%10\n",
    "        dict = defaultdict(int)\n",
    "        while True:\n",
    "            tmp = 0\n",
    "            while p:\n",
    "                tmp += q*q\n",
    "                p//=10\n",
    "                q=p%10\n",
    "            p,q= tmp,tmp%10\n",
    "            print(tmp)\n",
    "            if tmp == 1:\n",
    "                return True\n",
    "            elif tmp in dict:\n",
    "                return False\n",
    "            else:\n",
    "                dict[tmp]+=1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        self.set = set()\n",
    "        self.flag = False\n",
    "\n",
    "        def rec(n) -> bool:\n",
    "            num = 0\n",
    "            for i in str(n):\n",
    "                num += int(i) * int(i)\n",
    "            if num == 1:\n",
    "                print(num)\n",
    "                self.flag =  True\n",
    "            if num in self.set:\n",
    "                return False\n",
    "            self.set.add(num)\n",
    "            print(num)\n",
    "            rec(num)\n",
    "        print(rec(n))\n",
    "        return self.flag\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        seen=set()\n",
    "        while 1:\n",
    "            n=str(n)\n",
    "            cnt=0\n",
    "            for i in n:\n",
    "                cnt+=int(i)**2\n",
    "            n=cnt\n",
    "            if n==1:\n",
    "                return True\n",
    "            if n in seen:\n",
    "                return False\n",
    "            seen.add(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        def get_next(n):\n",
    "            total_sum=0\n",
    "            while n>0:\n",
    "                n,digit=divmod(n,10)\n",
    "                total_sum+=digit**2\n",
    "            return total_sum\n",
    "        \n",
    "        seen=set()\n",
    "        while n!=1 and n not in seen:\n",
    "            seen.add(n)\n",
    "            n=get_next(n)\n",
    "        \n",
    "        return n==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isHappy(self, n: int) -> bool:\n",
    "        def get_next(n):\n",
    "            total_sum = 0\n",
    "            while n > 0:\n",
    "                n, digit = divmod(n, 10)\n",
    "                total_sum += digit ** 2\n",
    "            return total_sum\n",
    "\n",
    "        seen = set()\n",
    "        while n != 1 and n not in seen:\n",
    "            seen.add(n)\n",
    "            n = get_next(n)\n",
    "        return n == 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
